<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>


<title>Sphere Online Judge (SPOJ)  - Problem EZDIJKST</title>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-2" id="metatag">
<meta name="Keywords" content="programming, language, algorithm, spoj, contest, contester, Java, C#, Pascal, C, C++, python, ruby, caml, ocaml, perl, haskell, lisp, prolog, fortran, assembler, asembler, functional, online, judge, problem, problemset, ACM">

<link href="http://www.spoj.pl/gfx/favicon.png" rel="shortcut icon" type="image/x-icon">
<link href="http://www.spoj.pl/rss/" rel="alternate" type="application/rss+xml" title="RSS Feed">
<link href="spoj-03700_files/style.css" rel="stylesheet" type="text/css" id="theme">
<link href="spoj-03700_files/tooltips.css" rel="stylesheet" type="text/css" id="theme">
<script type="text/javascript" src="spoj-03700_files/jquery_004.js"></script>
<style type="text/css">
<!--
.maintable {width: 755px;} 
-->
</style>
<script type="text/javascript" language="javascript">
<!--
function UnCryptMailto(s) {
	var n=0;
	var r="";
	for(var i=0;i<s.length;i++) {		
		n=s.charCodeAt(i); 
		if (n>=8364) {n = 128;}
		r += String.fromCharCode(n+(2));	
	}
	return r;
}
function linkTo_UnCryptMailto(s)	{
	location.href=UnCryptMailto(s);
}
// -->
</script>

</head><body>
<center>
<table class="maintable" id="maintable" cellpadding="10" cellspacing="0">
<tbody><tr>
    <td colspan="2" class="header">
        <table border="0" cellpadding="0" cellspacing="0" width="100%">
        <tbody><tr>
		<td class="headerleft">
		</td><td class="headercenter">
<h1><img alt="Sphere Online Judge" title="Sphere Online Judge" src="spoj-03700_files/sphere-spoj-small.png" style="margin-top: -4px; margin-bottom: -4px;" border="0"></h1>
		</td>
		<td class="headerright">
	</td></tr>
	</tbody></table>
    </td>
</tr>
<tr><td class="menu" valign="top" width="92">


<div class="menucmd"><a href="http://www.spoj.pl/logout"><b style="font-weight: normal;">Log Out</b></a><br><b style="font-weight: normal; margin-right: -100px;">dncampo</b><br><hr><a href="http://www.spoj.pl/myaccount">my account</a><br><a href="http://www.spoj.pl/tutorials">tutorials</a><br><br><a href="http://www.spoj.pl/status">status</a><br><a href="http://www.spoj.pl/submit">submit</a><br><a href="http://www.spoj.pl/problems/classical/">problems</a><br><a href="http://www.spoj.pl/search">search</a><br><br><a href="http://www.spoj.pl/">news</a><br><a href="http://www.spoj.pl/contests">contests</a><br><a href="http://www.spoj.pl/ranks/">ranks</a><br><br><a href="http://www.spoj.pl/forum">forum</a><br><a href="http://www.spoj.pl/comments">comments</a><br><a href="http://www.spoj.pl/credits">credits</a><br><hr></div><a href="http://www.spoj.pl/problems/classical/"></a><br>

	<div class="time">
Server time:</div>
<div class="time">
2009-09-01
<br>
<b>17 : 06 : 20</b>
</div>

</td>
<td style="padding: 0px;" class="content0" valign="top">
        <table cellpadding="0" cellspacing="0" width="100%">
        <tbody><tr>
                <td style="padding: 0px;" colspan="2"><center>
                                
                </center></td>
        </tr>
        <tr>
                <td class="content" style="padding: 10px;" width="99%">
	<script type="text/javascript" src="spoj-03700_files/jquery_002.js"></script>
<script type="text/javascript" src="spoj-03700_files/jquery_003.js"></script>
<script type="text/javascript" src="spoj-03700_files/jquery.js"></script>


	 <!-- wykorzystywane w pcontent.html (by wiele) -->
	
	<table class="problems" width="100%">
	<tbody><tr class="navigation">
			<td><a href="http://www.spoj.pl/submit/EZDIJKST/">Submit</a></td>
			<td><a href="http://www.spoj.pl/status/EZDIJKST,dncampo/">My submissions</a></td>
		<td><a href="http://www.spoj.pl/status/EZDIJKST/">All submissions</a></td>
	<td><a href="http://www.spoj.pl/ranks/EZDIJKST/">Best solutions</a></td>
	<td><a href="http://www.spoj.pl/problems/EZDIJKST.ps">PS</a></td>
	<td><a href="http://www.spoj.pl/problems/EZDIJKST.pdf">PDF</a></td>
	<td><a href="http://www.spoj.pl/problems/classical/">Back to list</a></td>
	</tr>
	</tbody></table>

	<div class="prob">


	<!-- plik z pomoca kontekstowa (cxhelp_*) dziedziczony po pindex.html -->


<table style="margin-top: 10px;" width="100%">
<tbody><tr>
	<td>
		<h2>SPOJ Problem Set (tutorial)</h2>
		<h1>3700. Easy Dijkstra Problem</h1>
		<h2>Problem code: EZDIJKST</h2>
	</td>
	</tr>
</tbody></table>

<p align="justify">
</p><p>Determine the shortest path between the specified vertices in the graph given in the input data.<br>
Hint: You can use Dijkstra's algorithm.<br>
Hint 2: if you're a lazy C++ programmer, you can use set and cin/cout (with sync_with_stdio(0)) - it should suffice.<br>
<br>
</p><h3>Input</h3>
<p>first line - one integer - number of test cases<br>
For each test case the numbers V, K (number of vertices, number of edges) are given,<br>
Then K lines follow, each containing the following numbers separated by a single space: <br>
a<sub>i</sub>, b<sub>i</sub>, c<sub>i</sub><br>
It means that the graph being described contains an edge from a<sub>i</sub> to b<sub>i</sub>,<br>
with a weight of c<sub>i</sub>.<br>

Below the graph description a line containing a pair of integers A, B is present.<br>

The goal is to find the shortest path from vertex A to vertex B.<br>
All numbers in the input data are integers in the range 0..10000.<br>

</p><h3>Output</h3>
<p>For each test case your program should output (in a separate line) a
single number C - the length of the shortest path from vertex A to
vertex B. In case there is no such path, your program should output a
single word "NO" (without quotes)<br>

</p><h3>Example</h3>

<pre><b>Input:</b>
3
3 2
1 2 5
2 3 7
1 3
3 3
1 2 4
1 3 7
2 3 1
1 3
3 1
1 2 4
1 3

<b>Output:</b>
12
5
NO
</pre>


<hr>
<table style="margin-bottom: 10px;" class="probleminfo" align="left" border="0" cellpadding="0" cellspacing="0">
<tbody><tr><td>Added by:</td><td><a href="http://www.spoj.pl/users/er2er">Robert Rychcicki</a></td></tr>
<tr><td>Date:</td><td>2009-01-10</td></tr>
<tr><td>Time limit:</td><td>1s
</td></tr>
<tr><td>Source limit:</td><td>50000B</td></tr>
<tr><td>Languages:</td><td>All </td></tr>

	
</tbody></table>
	<div id="ccontent">
	
<hr style="clear: both;">

<a id="comments"></a>
<table id="comments_table" width="100%">
	
</table>


<script language="javascript" type="text/javascript">
<!--
function getCookieVal (offset) {
        var endstr = document.cookie.indexOf (";", offset);
        if (endstr == -1) { 
                endstr = document.cookie.length; 
        }
        return unescape(document.cookie.substring(offset, endstr));
}

function GetCookie (name) {
  var arg = name + "=";
  var alen = arg.length;
  var clen = document.cookie.length;
  var i = 0;
  while (i < clen) {
    var j = i + alen;
    if (document.cookie.substring(i, j) == arg) {
      return getCookieVal (j);
      }
    i = document.cookie.indexOf(" ", i) + 1;
    if (i == 0) break; 
    }
  return null;
}

function toggleComments() {
        var a = document.getElementById('comments_table');
        var d = a.style.display;
        if( d == "" || d == "block" ){
                d = "none";
                document.getElementById('comments_sh').innerHTML = 'show';
        } else {
                d = "block";
                document.getElementById('comments_sh').innerHTML = 'hide';
        }
        a.style.display = d;
        document.cookie="comments_table="+d+"; path=/;";
}

if( GetCookie('comments_table') == 'none' ){
        document.getElementById('comments_sh').innerHTML = 'show';
        document.getElementById('comments_table').style.display = 'hide';
}

-->
</script>


	</div>
	<table width="100%">
                <tbody><tr>
                <td colspan="2" height="20"></td>
        </tr>
        <form method="post" action="/comment/EZDIJKST/add/"></form>
        <tr> <td style="padding-left: 5px;" colspan="2">Leave a Comment</td> </tr>
        <tr>
                <td valign="top"></td>
                <td><textarea name="content" cols="40" rows="3"></textarea></td>
        </tr>
                <tr>
                <td colspan="2" style="padding-left: 5px;">
                        <input value="Publish" type="submit">
                        <input name="pcode" value="EZDIJKST" type="hidden">
                </td>
        </tr>
<tr>
<td colspan="2" class="smallgrey" style="padding-left: 5px;">
Notes:
<br>1. Don't post any source code here.
<br>2. Please be careful, leave short comments only. Don't spam here.
<br>3. For more discussion (hints, ideas, solutions) please visit our <a href="http://www.spoj.pl/forum">forum</a>.
<br>4. Authors are allowed to delete the post and use html code here (e.g. to provide some useful links).
</td>
</tr>
        
        </tbody></table>

	</div>
        </td>
</tr><tr>
        <td style="padding: 0px;" colspan="2"><center>
                
</center></td>
</tr>
</tbody></table>
</td>
</tr>

<tr>
<td colspan="2" class="footer">

<script language="javascript" type="text/javascript">
<!--
function swapSheet(sheet, caller) {
    document.getElementById('theme').href=sheet;
    document.cookie="css_0="+sheet+"; path=/;";
    caller.href="#bottom";
}

function setWidth(w, caller) {
    document.getElementById('maintable').style.width=w;
    document.cookie="res="+w+"; path=/;";
    caller.href="#bottom";
}
//-->

</script>
        <table width="100%">
    <tbody><tr>
	<td class="cfooter" align="left" width="10%">
	<a href="http://www.spoj.pl/info/">About SPOJ</a>
	</td>
	<td class="cfooter" align="center">
	    page size:
	    <a href="http://www.spoj.pl/?rsl=755px" onclick="setWidth('755px', this)">800x600</a>
	    <a href="http://www.spoj.pl/?rsl=980px" onclick="setWidth('980px', this)">1024x768</a>
	    <a href="http://www.spoj.pl/?rsl=100%" onclick="setWidth('100%', this)">Full</a>
	    &nbsp;&nbsp;
	    theme:
	    <a href="http://www.spoj.pl/?css=/themes/skin1.css" onclick="swapSheet('/themes/skin1.css', this)">olive</a>
	    <a href="http://www.spoj.pl/?css=/themes/skin2.css" onclick="swapSheet('/themes/skin2.css', this)">banana</a>
	    <a href="http://www.spoj.pl/?css=/themes/skin3.css" onclick="swapSheet('/themes/skin3.css', this)">plum</a>
	</td>
		<td class="cfooter" align="center">
		 <span title="The discussion channel of the Sphere Online Judge community.">
		 <a href="irc://irc.freenode.net/spoj"><b>#spoj</b> at freenode</a>
		 </span>
	</td>
		<td class="cfooter" style="text-align: right;" width="10%">
		<a href="http://www.spoj.pl/rss/"><img src="spoj-03700_files/rss10x10.gif" border="0">&nbsp;RSS</a>&nbsp;
	
	</td>
    </tr>
    </tbody></table>
    </td></tr></tbody></table>
</center>
<div style="font-size: 10px; margin-top: 4px; color: rgb(85, 80, 95);"><center>
<a href="http://www.spoj.pl/" style="color: black;">SPOJ</a>
System &#169; 2008-2009
<a href="http://sphere-research.com/" style="color: black;">Sphere Research Labs</a>. 
All Rights Reserved.</center></div>
</body></html>